#include <iostream>
#include <stdlib.h>
#include <time.h>
#include <unistd.h>
#define random(x) (rand()%x)

using namespace std;

class Spirit{
	
public:
  Spirit() //在类里和类名同名的函数称为构造函数，这个函数在用类定义对象的时候会由C++的编译器自动调用，这样就能达到初始化的效果
  {

	  quei = new int[m * n];
	  quej = new int[m * n];
	  prep = new int[m * n];
	  head = 0;
	  rear = 1;
	  length = 1;
	  quei[head] = 1;
	  quej[head] = 1;
	  prep[head] = -1;
	
	
	}
	
	~Spirit()
	{
		delete []quei;
		delete []quej;
		delete []prep;
	}
	
	void new_space(int m1, int n1);//分配空间
	
	void delete_space(int m1);//释放空间
	
	void Maze_Runner();//移动精灵
	
	void Building_labyrinth();//创建迷宫
	
private:
	int **p;//定义一个二维的int数组
	int m,n;
	int *quei;//储存行坐标队列
	int *quej;//储存列坐标队列
	int *prep;//储存之前一步在队列中的位置
	
	
	int head,rear,length;//队列头，队列尾，队列长度
	int pos;//当前节点在队列中的位置
	int ci,cj,ni,nj;//当前节点坐标 新节点坐标
	int dir;//移动方向
};


	 /* 分配空间*/
void Spirit::new_space(int m1, int n1)
{
	m=m1;
	n=n1;
	//
	//创建行指针
	p=new int*[m+2];
	//为每一行分配空间
	for(int i=0;i<=m+1;i++)
	{
	p[i] = new int [n+2];
	}
}
/*释放空间*/
void Spirit::delete_space(int m1)
{
	m=m1;
	
	for(int i=0;i<=m+1;i++){
		
		delete[] p[i];
	}
		delete[] p;


}

/*创建迷宫*/
void Spirit::Building_labyrinth()
{
	srand((int)time(0));
	for(int i=0;i<=m+1;i++)
	{
		for(int j=0;j<=n+1;j++)
		{
			if(i==0|j==0|i==m+1|j==n+1)
			{
				p[i][j]=1;
			}
			else
			{
				int x=random(50);
				if(x<=1)

				{
					p[i][j]=1;
				}
				else
				{
					p[i][j]=0;

				}	
			}
					if(p[i][j]==0)
						cout<<" ";
					else
						cout<<"#";
		}			
				cout<<endl;
	}
	
	
} 

/*移动精灵*/
void Spirit::Maze_Runner() 
{
	int move[8][2] = {0,1,1,0,0,-1,-1,0,-1,-1,-1,1,1,-1,1,1} ;
	if(p[1][1]==1)//第一点为1无法通过
		length=0;
	else
		p[1][1]=1;
	
	while(length)//队列不为空则继续
	{
		for(pos=head;pos<head+length;pos++)//遍历所有节点
		{
			ci=quei[pos];cj=quej[pos];//当前位置坐标
			if(ci==m&&cj==n)
				break;
			for(dir=0;dir<8;dir++)//寻找八个方向
			{
				ni=ci+move[dir][0];nj=cj+move[dir][1];
				if(p[ni][nj]==0)//假如没有走过
				{
					quei[rear]=ni;quej[rear]=nj;prep[rear]=pos;//新节点入队
					rear=rear+1;
					p[ni][nj]=1;//标记已经走过
				}
			}
		}
		if(ci==m&&cj==n)
			break;
			head=head+length;
			length=rear-head;//节点出列

	}
	if(ci==m&&cj==n)
	{
		while(pos!=-1)
		{
			cout<<'('<<quei[pos]<<','<<quej[pos]<<')';
			pos=prep[pos];
			if(pos!=-1)
				cout<<',';
		}
		cout<<endl;
	}
	
	else
	{
		cout<<"无路可走"<<endl;
	}
	
}


int main()
{
	//定义一个精灵对象
	Spirit Smurfs;
	int m1,n1;
	cout<<"请输入迷宫规格：";
	cin>>m1>>n1;
	
	Smurfs.new_space(m1,n1);
	
	Smurfs.Building_labyrinth();
	
	Smurfs.Maze_Runner(); 

	Smurfs.delete_space(m1);
	
	return 0;
}
